/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        503.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/18 11:04
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。
//数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，
//这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
#include "../header.h"
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans(n);
        stack<int> stack;
        for (int i = 2 * n - 1; i >= 0; --i) {
            while (!stack.empty() && nums[i % n] >= stack.top()){
                stack.pop();
            }
            ans[i % n] = stack.empty() ? -1 : stack.top();
            stack.push(nums[i % n]);
        }
        return ans;
    }
};

